package com.zhanghp.class038;

import java.util.Stack;

import static com.zhanghp.common.StackUtil.*;

/**
 * <p>
 * 用递归函数排序栈
 * <p>
 * 栈只提供push、pop、isEmpty三个方法
 * <p>
 * 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
 * <p>
 * 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
 * <p>
 * 除此之外不能使用任何的容器，数组也不行
 * <p>
 * 就是排序过程中只能用：
 * <p>
 * 1) 栈提供的push、pop、isEmpty三个方法
 * <p>
 * 2) 递归函数，并且返回值最多为单个整数
 * <hr/>
 * <p>
 * 递归调用，就是一个一个空间的调用
 * </p>
 *
 * @author zhanghp
 * @since 2024/6/20 15:29
 */
public class Code06_SortStackWithRecursive {

    public static void main(String[] args) {
        final int test_time = 10_000;
        int N =20;
        int V = 20;
        System.out.println("测试开始");
        for (int i = 0; i < test_time; i++) {
            Stack<Integer> random = random(N, V);
            sort(random);
            if (!checkSort(random)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");
    }
    public static void sort(Stack<Integer> stack) {
        int deepth = deepth(stack);
        while (deepth > 0) {
            // 指定栈深度
            // 1. 获取当前栈的最大值
            int max = max(stack, deepth);
            // 2. 获取指定最大值出现的次数
            int times = times(stack, deepth, max);
            // 3. 把此数进行下沉
            down(stack, deepth, max, times);
            // 4. 处理完出现几次后，用deepth减掉，进行下一个数的排序
            deepth -= times;
        }
    }

    // 返回栈的深度
    // 不改变栈的数据状况
    public static int deepth(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return 0;
        } else {
            int pop = stack.pop();
            int deepth = deepth(stack) + 1;
            stack.push(pop);
            return deepth;
        }
    }

    // 从栈当前的顶部开始，往下数deep层
    // 返回这deep层里的最大值
    public static int max(Stack<Integer> stack, int deep) {
        if (deep == 0) {
            return Integer.MIN_VALUE;
        } else {
            Integer pop = stack.pop();
            int max = Math.max(max(stack, deep - 1), pop);
            stack.push(pop);
            return max;
        }
    }

    // 从栈当前的顶部开始，往下数deep层，已知最大值是max了
    // 返回，max出现了几次，不改变栈的数据状况
    public static int times(Stack<Integer> stack, int deep, int max) {
        if (deep == 0) {
            return 0;
        } else {
            int pop = stack.pop();
            // 从deep，往上，一个一个比较，是否相等max，相等为1
            int restTimes = times(stack, deep - 1, max);
            // 一定要加括号！！！
            // 否则会变成，(restTimes + pop) == max ? 1 : 0
            int times = restTimes + (pop == max ? 1 : 0);
            stack.push(pop);
            return times;
        }
    }

    // 从栈当前的顶部开始，往下数deep层，已知最大值是max，出现了k次
    // 请把这k个最大值沉底，剩下的数据状况不变
    // deep 的意义： 排序好的大数已经在最底下，用deep来鉴别下一个大数放哪
    public static void down(Stack<Integer> stack, int deep, int max, int times) {
        if (deep == 0) {
            // 直接塞进去，然后else里判断若和max相等，则不push
            for (int i = 0; i < times; i++) {
                stack.push(max);
            }
        } else {
            Integer pop = stack.pop();
            down(stack, deep - 1, max, times);
            // 不相等则不处理
            if (pop != max) {
                stack.push(pop);
            }
        }
    }





}
